package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 随机快速排序--->左神快排3.0版本
 *
 * 荷兰国旗问题
 *
 * @author Api
 * @date 2022/11/19 18:35
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 2, 1, 34, 2};//给定一个数组
        quickSort(arr, 0, arr.length-1); //的带排序后的数组
        System.out.println(Arrays.toString(arr));//打印输出得到数组
    }


    /*arr[1...r]排好序*/
    public static void quickSort(int[] arr, int L, int R){
        if (L<R){
            //随机，等概率事件，时间复杂度为N*logN
            swap(arr, L+(int)(Math.random()* (R-L+1)), R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0]-1);//<区
            quickSort(arr, p[1]+1, R);//>区
        }
    }
    /*
        这是一个处理arr[1...r]的函数
    *   默认以arr[r]做划分，arr[r]->p  <p  ==p  >p
        返回等于区域（左边界，右边界），返回一个长度为2的数组res，res[0] res[1]
    * */
    public static int[] partition(int[] arr, int L, int R){
        int less = L-1;//<区右边界
        int more = R;//>区左边界
        while(L<more){//L表示当前数的位置 arr[R] -> 划分值
            if (arr[L]<arr[R]){//当前数<划分值
                swap(arr, ++less, L++);
            }else if(arr[L]> arr[R]){//当前数>划分值
                swap(arr, --more, L);
            }else{
                L++;
            }
        }
        swap(arr, more, R);
        return new int[]{less+1, more};
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
